\section{Comparación Algoritmos}
\subsection{Introducción}
En esta sección presentaremos diferentes tests interesantes y analizaremos los resultados obtenidos. Estudiaremos la comparación entre los diferentes algoritmos a la hora de tratar de minimizar la suma total de los circuitos que cumplan con lo pedido en el enunciado.

Además, volveremos a hacer los tests con un grafo con pesos random entre uno y 5000. Elegimos este número ya que teníamos que poner un límite superior a los pesos de los ejes y esta constante no nos pareció ni demasiado chica ni demasiado grande.

\subsection{Tests hechos}
Decidimos hacer 6 tests que en un principio nos parecieron interesantes:
\begin{compactitem}
 \item Comparar las soluciones de todos los algoritmos menos el exacto
 \item Comparar Tabu contra Local
\end{compactitem}

\subsubsection{Comparar las soluciones de todos los algoritmos menos el exacto}
En este caso, queríamos ver la diferencia entre las sumas obtenidas de los \textit{algoritmos heurísticos} para ver si realmente tabú trabajaba mejor que la constructiva y la local, y además si alguno de estos dos últimos era claramente mejor que el otro.

Entonces, para testear lo que hicimos fue ejecutar 115 grafos con cantidad de nodos entre 5 y 120 (distribuidos equitativamente entre los 115 posibles valores) con los 3 algoritmos, la constructiva recibiendo a una solución \textit{random-mente-mala} como solución y tabú recibiendo el resultado de la constructiva como solución inicial.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/TestSolMenosExacto_con_mala.png,width=0.9\linewidth,clip=}
\caption{Análisis de la ejecución de Tabú y Local con solución inicial \textit{mala}.}
\end{figure}

Como se esperaba, los pesos de la solución mala son mucho peores que los pesos de los \textit{heurísticos}. Además, la diferencia aumenta considerablemente acorde aumenta la cantidad de nodos mostrando que mientras mayor sea el n, mejor va a ser usar las heurísticas antes que elegir dos circuitos random, que sería básicamente lo que hace la solución mala. Esto habla muy bien de las heurísticas ya que significa que no se \textit{caen} para casos relativamente grandes, sino que van manteniendo un \textit{nivel de eficiencia} acorde aumenta el n.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/TestSolMenosExacto_sin_mala.png,width=0.9\linewidth,clip=}
\caption{Análisis de la ejecución de Tabú y Local con solución inicial \textit{mala}.}
\end{figure}

Si prestamos más atención a la relación entre las 3 heurísticas, veremos que en todos los casos la heurística \texttt{Tabú} es mejor que las otras dos, como se esperaba. En algunos casos es grande la diferencia entre ésta y las demás, pero en otros casos no tanto.


En los casos más chicos (n menor a 40) aparenta no haber una \textit{superioridad} clara de la constructiva sobre la búsqueda local y viceversa, ya que hay casos en la que las dos están segundas después de la tabú en términos de eficacia, dejando a la otra como 3era. 

En cambio, desde 40 en adelante, la heurística constructiva parece sacar ventaja, ya que sólo en unos pocos casos queda tercera, y el resto queda como segunda dejando a la búsqueda local como 3era. Y como son los casos grandes los que importan muchas veces en la práctica, si por alguna razón no pudiéramos aplicar la meta-Heurística Tabú, nos decidiríamos por la heurística constructiva antes que la Local, si nos basamos en lo mostrado por este gráfico.

\subsubsection{Comparar Tabú contra Local}
Para ver la diferencia entre eficiencia de Local y Tabú decidimos hacer este test que se basa en pasarle a ambos la misma solución inicial y comparar los resultados obtenidos en casa caso.

Para ello, corrimos 30 grafos con la cantidad de nodos de todos ellos entre 150 y 50, con diferencia de 3 nodos entre uno y su siguiente ( $\lfloor(150-50)/3\rfloor$ = 3) y nos guardábamos el resultado de aplicar Tabú y Local a ese grafo. Además, lo hicimos dos ocasiones: una recibiendo ese grafo y una solución mala, y otra recibiendo la solución resultado de la constructiva.

Nota: al tabú lo ejecutamos con \texttt{cantidad de iteraciones = 10*n} y \texttt{longitud de la lista = 2.4*n}, ya que, por los tests anteriores, nos aseguran una buena solución.


\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/tabu_vs_local_con_mala.png,width=0.9\linewidth,clip=}
\caption{Análisis de la ejecución de Tabú y Local con solución inicial \textit{mala}.}
\end{figure}

Como se puede ver en la Figura 8, se encuentran los valores para las soluciones dadas por los algoritmos de búsqueda local y heurística Tabú, siendo la solución inicial mala o  poco óptima. Se puede apreciar que en todos los casos, la metaheurística Tabú siempre obtiene soluciones mejores que las obtenidas por búsqueda local. En algunos instancias, la diferencia entre Local y Tabú es grande para una misma instancia de entrada, mientras que en otros casos, la mejora de Tabú respecto a Búsqueda Local es casi imperceptible.\\

\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/tabu_vs_local_con_const.png,width=0.9\linewidth,clip=}
\caption{Análisis de la ejecución de Tabú y Local con la solución de la constructiva como inicial.}
\end{figure}

En el gráfico 9, se puede ver que lo mismo sucede cuando la solución inicial es generada por la heurística constructiva. En todos los casos, la metaheurística Tabú mejora el resultado obtenido mediante búsqueda local. \\
Comparando los dos gráficos, se puede ver que para un número fijo de nodos en un grafo, las instancias inciales generadas por la heurística constructiva derivan en un mejor resultado en búsqueda local y Tabú, al compararlas con los resultados de búsqueda local y Tabú derivados de una solución inicial mala.\\

% //		comparar_sols_tabu_vs_local(150,50, 30, 240, 1000); //hasta 150 nodos por grafo, desde 50 nodos por grafo, 30 grafos en total 240% del n para lista. 1000% del n para iteraciones
\subsection{Gráficos}



% \subsection{Comparación Rendimiento}
% Para los tests de rendimiento en esta sección del informe decidimos usar un medidor de tiempo en vez de los contadores de operaciones propios que veníamos usando ya que sería muy difícil, para no decir imposible, medir con la misma moneda todas las operaciones para poder comparar entre los diferentes algoritmos. Además, la \textit{inmunidad} a otros procesos y el mero sistema operativo que provee el método de contar operaciones no nos parece lo suficientemente importante.
% 
% En el primer test de rendimiento decidimos comparar el tiempo de ejecución entre el algoritmo exacto, algoritmo constructivo, búsqueda local y tabú. Para estos dos últimos, ya que requerían una solución inicial, decidimos darles una solución \textit{mala} aunque es irrelevante para el rendimiento si no analizamos la eficacia. La misma que en los tests de sus respectivas secciones.
% 
% Para el primer test, medimos el \textbf{tiempo} de ejecutar los 4 algoritmos para grafos con nodos desde 5 hasta 10 con pesos aleatorios en los ejes.
% 
% \begin{figure}[H]
% \centering
% \epsfig{file=./graficos/TestsFinales/TestRendTodos.png,width=0.9\linewidth,clip=}
% \caption{Análisis de rendimiento todos para grafos desde 5 hasta 10 nodos. Parámetros Tabú: Longitud 20 de lista y 7 iteraciones como parámetros.}
% \end{figure}
% 
% Nada sorprendente: el exacto le gano a todos, tabú quedó segundo, búsqueda local tercero y constructiva por último. Decimos que es nada sorprendente ya que la complejidad del exacto es exageradamente grande, el tabú usa reiteradas veces a la búsqueda local y por ende será más complejo computacionalmente hablando y la constructiva es el más simple computacionalmente hablando de todos.
% 
% \begin{figure}[H]
% \centering
% \epsfig{file=./graficos/TestsFinales/TestRendMenosExacto.png,width=0.9\linewidth,clip=}
% \caption{Análisis de rendimiento constructiva, búsqueda local y Tabú. Parámetros Tabú: Longitud 20 de lista y 7 iteraciones como parámetros.}
% \end{figure}
% 
% En este caso nos encontramos con algunos outliers, pero dado que estamos midiendo con tiempo y todos parecen ocurrir en un ``pico'' en el que van creciendo mientras se acercan al pico y van disminuyendo mientras lo van pasando y los tres tienen comportamientos parecidos en el mismo tiempo (íbamos testeando una instancia con todos en vez de uno por uno) podemos concluir que habrá sido por culpa del scheduler o algún programa que interfirió con nuestro testeo.
% 
% \subsection{Comparación Eficacia}
% En el primer test de eficacia decidimos testear la eficacia de todos los algoritmos en un grafo dado de 10 nodos con pesos de los ejes con distribución aleatoria.
% 
% \begin{figure}[H]
% \centering
% \epsfig{file=./graficos/TestsFinales/grafodieznodos.png,width=0.9\linewidth,clip=}
% \caption{Análisis de resultados entre exacto, constructiva, búsqueda local y Tabú con diferentes soluciones iniciales. Parámetros Tabú: Longitud 20 de lista y 7 iteraciones como parámetros.}
% \end{figure}
% 
% Como fuimos cambiando sólo la solución inicial \textit{mala} mientras el grafo seguía siendo el mismo, sólo podíamos obtener una posible solución para el algoritmo exacto y también sólo una posible para la constructiva ya que ambos son determinísticos y no usan a la solución inicial mala sino que generan la suya desde cero.
% 
% En cambio, mientras vaya cambiando la solución \textit{mala} irá cambiando la eficacia de los algoritmos búsqueda local y tabú directamente proporcional.

% \begin{figure}[H]
% \centering
% \epsfig{file=./graficos/TestsFinales/TestSolMenosExacto.png,width=0.9\linewidth,clip=}
% \caption{Análisis de resultados entre exacto, constructiva, búsqueda local y Tabú con diferentes soluciones iniciales. Parámetros Tabú: Longitud 20 de lista y 7 iteraciones como parámetros.}
% \end{figure}


